#ifndef LIST_L_H

#define LIST_L_H

#include "status.h"
#include <iostream>
using namespace std;

template<typename T>
class List_l
{
private:
	struct Node
	{
		T data;
		Node * next;
	};

	Node * head;
	int length;
public:
	List_l();
	~List_l();
	Status InitList();
	Status DestroyList();
	Status ClearList();
	bool ListEmpty() const;
	int ListLength() const;
	Status GetElem(int index, T & e) const;
	int LocateElem(const T & e) const;
	Status PriorElem(const T & cur_e, T & pre_e) const;
	Status NextElem(const T & cur_e, T & next_e) const;
	Status ListInsert(int index, const T & e);
	Status ListDelete(int index, T & e);
	Status ListTraverse() const;
	Status ListDelete_range(T mink, T maxk);
	Status ListReverse();
};

template<typename T>
List_l<T>::List_l() : length(0)
{
	head = new Node;
	head->next = nullptr;
}

template<typename T>
List_l<T>::~List_l()
{
	Node * h_tmp = head;
	while (h_tmp != nullptr)
	{
		head = head->next;
		delete h_tmp;
		h_tmp = head;
	}
}

template<typename T>
Status List_l<T>::InitList()
{
	head = new Node;
	head->next = nullptr;
	return OK;
}

template<typename T>
Status List_l<T>::DestroyList()
{
	Node * h_tmp = head;
	while (h_tmp != nullptr)
	{
		head = head->next;
		delete h_tmp;
		h_tmp = head;
	}

	return OK;
}

template<typename T>
Status List_l<T>::ClearList()
{
	Node * h_tmp = head->next;
	head->next = nullptr;
	while (h_tmp != nullptr)
	{
		Node * next = h_tmp->next;
		delete h_tmp;
		h_tmp = next;
	}

	return OK;
}

template<typename T>
bool List_l<T>::ListEmpty() const
{
	return this->length == 0;
}

template<typename T>
int List_l<T>::ListLength() const
{
	return this->length;
}

template<typename T>
Status List_l<T>::GetElem(int index, T & e) const
{
	if (index >= this->length || index < 0)
		return ERROR;

	Node * h_tmp = head->next;
	while (index-- > 0)
		h_tmp = h_tmp->next;
	e = h_tmp;

	return OK
}

template<typename T>
int List_l<T>::LocateElem(const T & e) const
{
	Node * h_tmp = head->next;
	int i = 0;
	while (h_tmp != nullptr)
	{
		if (e == h_tmp->data)
			return i;
		++i;
	}
	return ERROR;
}

template<typename T>
Status List_l<T>::PriorElem(const T & cur_e, T & pre_e) const
{
	Node * h_tmp = head->next;
	while (h_tmp != nullptr)
	{
		if (h_tmp->next->data == cur_e)
		{
			pre_e = h_tmp->data;
			return OK;
		}
		h_tmp = h_tmp->next;
	}

	return ERROR;
}

template<typename T>
Status List_l<T>::NextElem(const T & cur_e, T & next_e) const
{
	Node * h_tmp = head;
	for (int i = 0; i < this->length - 1; i++)
	{
		if (h_tmp->data = cur_e)
		{
			next_e = h_tmp->next;
			return OK;
		}
	}

	return ERROR;
}

template<typename T>
Status List_l<T>::ListInsert(int index, const T & e)
{
	if (index < 0 || index > this->length)
		return ERROR;

	Node * h_tmp = head;
	int i = 0;
	while (i++ < index)
		h_tmp = h_tmp->next;
	Node * tmp = new Node;
	tmp->data = e;
	tmp->next = h_tmp->next;
	h_tmp->next = tmp;

	++this->length;

	return OK;
}

template<typename T>
Status List_l<T>::ListDelete(int index, T & e)
{
	if (index < 0 || index >= this->length)
		return ERROR;

	Node * h_tmp = head;
	int i = 0;
	while (i++ < index)
		h_tmp = h_tmp->next;
	Node * d_tmp = h_tmp->next;
	e = d_tmp->data;
	h_tmp->next = h_tmp->next->next;
	delete d_tmp;

	--this->length;

	return OK;
}

template<typename T>
Status List_l<T>::ListTraverse() const
{
	if (ListEmpty())
		return ERROR;

	Node * h_tmp = head->next;
	while (h_tmp != nullptr)
	{
		cout << h_tmp->data << endl;
		h_tmp = h_tmp->next;
	}

	return OK;
}

template<typename T>
Status List_l<T>::ListDelete_range(T mink, T maxk)
{
	Node * h_tmp = head->next;
	int i = 0;
	while (h_tmp != nullptr)
	{
		if (h_tmp->data > mink && h_tmp->data < maxk)
		{
			Node * d_tmp = h_tmp;
			h_tmp = h_tmp->next;
			T tmp;
			ListDelete(i, tmp);
		}
		else
		{
			++i;
			h_tmp = h_tmp->next;
		}
	}

	return OK;
}

template<typename T>
Status List_l<T>::ListReverse()
{
	Node * newbase = new Node;
	if (newbase == nullptr)
		return OVERFLOW;
	newbase->next = nullptr;

	Node * h_tmp = head->next;
	for (int i = 0; i < this->length; i++)
	{
		Node * newNode = new Node;
		if (newNode == nullptr)
			return OVERFLOW;
		newNode->data = h_tmp->data;
		newNode->next = newbase->next;
		newbase->next = newNode;

		h_tmp = h_tmp->next;
	}
	int len = this->length;
	DestroyList();
	this->head = newbase;

	return OK;
}


#endif